package com.lmk.dsa.algorithm.graph.shortestPath;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import com.lmk.dsa.struct.commons.Edge;
import com.lmk.dsa.struct.graph.Graph;
import com.lmk.dsa.struct.heap.MinIndexHeap;

/**
 * 贝尔曼-福特（BellmanFord）单源最短路径算法，可以处理负权边
 * @author LaoMake
 * @since 1.0
 */
public class BellmanFord {

    /** 图 */
    private Graph graph;

    /** 顶点的总数 */
    private int n;

    /** 起始节点索引 */
    private int source;

    /** 是否包含负权环 */
    boolean hasNegativeCycle;

    /** 从起始节点到目标节点的最小权值数组 */
    private int[] distTo;

    /** 节点访问状态数组 */
    private boolean[] marked;

    /** 标记索引位置的节点通过哪条边到达 */
    private Edge[] from;

    /** 最小索引堆 */
    private MinIndexHeap indexHeap;

    public BellmanFord(Graph graph, int source) {
        this.source = source;
        this.graph = graph;
        n = graph.vertexSize();
        distTo = new int[n];
        marked = new boolean[n];
        from = new Edge[n];
        indexHeap = new MinIndexHeap(n);
        shortestPath();
    }

    /**
     * 检测负权环
     * @return
     */
    private boolean detectNegativeCycle(){
        List<Edge> adjEdgeList;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                adjEdgeList = graph.adjoinEdge(j);
                for (Edge e : adjEdgeList){
                    if(from[e.to] == null  || distTo[e.from] + e.weight < distTo[e.to]){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 求取最短路径
     */
    private void shortestPath(){
        distTo[source] = 0;      // 源点到自己路径为0
        marked[source] = true;   // 源点标记为已访问
        List<Edge> adjEdgeList;
        for (int pass = 0; pass < n; pass++) {
            for (int i = 0; i < n; i++) {
                adjEdgeList = graph.adjoinEdge(i);
                for (Edge e : adjEdgeList){
                    if(from[e.to] == null  || distTo[e.from] + e.weight < distTo[e.to]){
                        distTo[e.to] = distTo[e.from] + e.weight;
                        from[e.to] = e;
                    }
                }
            }
        }
        hasNegativeCycle = detectNegativeCycle();
    }

    /**
     * 判断是否可以到达目标节点
     * @param to
     * @return
     */
    public boolean hasPathTo(int to){
        assert to >=0 && to < n;
        return marked[to];
    }

    /**
     * 获取到指定节点的最短路径值
     * @param to
     * @return
     */
    public int shortestPathTo(int to){
        assert to >=0 && to < n;
        return distTo[to];
    }

    /**
     * 获取到达指定节点的最短路径（边）
     * @param to
     * @return
     */
    public List<Edge> shortestPath(int to){
        assert !hasNegativeCycle;

        // 查询完整路径
        Stack<Edge> stack = new Stack<>();
        Edge edge = from[to];
        while (edge != null && edge.from != edge.to){
            stack.push(edge);
            edge = from[edge.from];
        }

        // 依次将栈内边取回
        List<Edge> edgeList = new ArrayList<>(stack.size());
        while (!stack.isEmpty()){
            edgeList.add(stack.pop());
        }

        return edgeList;
    }

    public boolean hasNegativeCycle() {
        return hasNegativeCycle;
    }

    /**
     * 打印到指定节点的最短路径
     * @param to
     */
    public void showPath(int to){
        List<Edge> edgeList = shortestPath(to);
        StringBuilder sb = new StringBuilder();
        for (Edge edge : edgeList){
            sb.append(edge.from).append(" -> ").append(edge.to).append("\n");
        }
        System.out.println(sb.toString());
    }
}
